// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏，实际上就是暴搜
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置
// 经典题目：全排列，子集

// 例题 6：
// 给你一个非负整数数组 nums 和一个整数 target 。
// 数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
//
//        例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
//        返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
//
//        示例 1：
//
//        输入：nums = [1,1,1,1,1], target = 3
//        输出：5
//        解释：一共有 5 种方法让最终目标和为 3 。
//        -1 + 1 + 1 + 1 + 1 = 3
//        +1 - 1 + 1 + 1 + 1 = 3
//        +1 + 1 - 1 + 1 + 1 = 3
//        +1 + 1 + 1 - 1 + 1 = 3
//        +1 + 1 + 1 + 1 - 1 = 3
//        示例 2：
//
//        输入：nums = [1], target = 1
//        输出：1
//
//
//        提示：
//
//        1 <= nums.length <= 20
//        0 <= nums[i] <= 1000
//        0 <= sum(nums[i]) <= 1000
//        -1000 <= target <= 1000

// 解题思路：
// 每次按顺序选择数组中 pos 位置的数字，使用 + 或者 -
// 下次选择 pos + 1位置的数字
// 当选完最后一个数字 且 找到目标和，收集结果

public class FindTargetSumWays {
    int ret = 0;
    int sum = 0;
    int t = 0;
    public int findTargetSumWays(int[] nums, int target) {
        t = target;
        dfs(nums, 0);
        return ret;
    }
    public void dfs(int[] nums, int pos){
        if(pos == nums.length){
            if(sum == t) ret++;
            return;
        }

        sum += nums[pos];
        dfs(nums, pos + 1);
        sum -= nums[pos];

        sum -= nums[pos];
        dfs(nums, pos + 1);
        sum += nums[pos];
    }
}
